package tree;

import sun.tools.tree.NegativeExpression;

/**
 * @author kaho
 * @since 2021/3/1
 */
public class _222_完全二叉树的节点个数 {

    /**
     * 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
     *
     * 完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/count-complete-tree-nodes
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param root
     * @return
     */
    public static int countNodes1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = getLevel1(root.left);
        int right = getLevel1(root.right);
        if (left==right) {
            return countNodes(root.right) + 1<<left;
        }else {
            return countNodes(root.left) + 1<<right;
        }
    }

    private static int getLevel1(TreeNode treeNode) {
        int level = 0;
        while (treeNode != null) {
            treeNode = treeNode.left;
            level++;
        }
        return level;
    }


    public static int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = getLevel(root.left);
        int right = getLevel(root.right);

        if (left== right) {
            return countNodes(root.right)+(1<<left);
        }else {
            return countNodes(root.left)+(1<<right);
        }
    }

    private static int getLevel(TreeNode root) {
        int heiht = 0;
        while (root!=null) {
            root = root.left;
            heiht++;
        }
        return heiht;
    }

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;
        treeNode3.left = treeNode6;
        int i = countNodes(treeNode1);
    }
}
